Certificates are used in the field of computer security, and often are included in public/private key cryptography-based systems. An example of public/private key cryptography is RSA public/private key cryptography. Computer security systems generally involve people or machines establishing their identity (authenticating) and communicating with other people or machines. Throughout this document, each user, server, node, computer, machine, system, entity, and so on participating in a security system is referred to as a principal. The use of this general term is intended to simplify the differences between participants and devices acting as their agents and to more clearly describe the interaction of the principals, whether they are humans or machines, or machines acting on the behalf of humans.
Generally, a principal's public key is publicly accessible. In some systems, all public keys are placed in one public place, such as on a server, or published, for example in a newspaper or in an electronic publication. But when all principals' keys are provided on a server or published with no other cryptographic protection, a principal cannot be sure that the published information is correct. An intruder might have overwritten the information in the server or replaced the published newspaper with a copy containing different information. If an intruder (“Irving”) can trick a principal Alice into believing that Irving's public key is principal Joe's public key, then Irving can impersonate Joe to Alice.
Authentication certificates are included in a security system to make it more difficult for an intruder to impersonate a principal. Authentication certificates are messages that specify a principal's name (i.e. Alice), the public key associated with that name (i.e. Alice's public key), and possibly other information. Certificates are digitally signed with a principal's private key. A digital signature is a cryptographic technique that allows a principal who knows the signer's public key to verify that the message was “signed” with the matching private key, meaning that the message came from the signer and that the message is intact.
In some systems, a principal known as a Certification Authority (“CA”) generates and issues authentication certificates. The certificates are signed with the CA's private key. In such systems, principals are somehow provided, for example systems can be pre-configured, with the CA's public key. All principals who know the CA's public key can verify the CA's signature on the certificates, and thereby determine that the certificates are intact (i.e. have not been tampered with) and that the signed certificate originates from the signer. Certificates can be stored in any convenient location, such as a directory service, or a principal can store its own certificate and furnish it as part of an authentication procedure. Certificates are relatively secure, because an intruder cannot modify them.
In such a system, it may become necessary to revoke a certificate, for example because a private key has been compromised, to revoke a user's privileges, or for other reasons. It is common practice to put an expiration date in a certificate, after which the certificate is invalid. It is also known (for example it is specified in the X.509 standard) for a certificate issuer to distribute or make available a certificate revocation list (“CRL”). A CRL includes a list of serial numbers of unexpired, revoked certificates and an issue time for the CRL. In such a system, a certificate is valid if it has a valid signature, has not expired, and is not listed in the issuer's most recent CRL. The use of a CRL adds overhead to the verification of a certificate, in that it requires the verifying system to obtain and check the CRL for the appearance of the certificate being validated.
A security system that uses a single CA that issues certificates requires that all principals trust and interact with the single CA. As the number of principals increases, this is often not possible. In some systems, a network is divided into domains. Each domain has a CA that services that domain's principals, and issues certificates for those principals. Each principal in a domain is provided with the public key of her domain's CA, and can thus verify certificates signed by her domain's CA. Principals communicating within the same domain operate as just described, verifying certificates signed by their domain's CA. But principals in different domains also need a way to verify the other principals' public keys.
It might be possible to provide all principals with the public keys for all CA's, however, it can be expensive, and is often impractical, for each principal to keep up-to-date as domains and CA's are added and removed from the system. Another solution is to have the CA in each domain be provided with the public keys for the CA's in each other domain. The CA can issue certificates that verify the public keys of the other domain. A principal communicating with a principal in another domain obtains a certificate from that other domain that is signed by the CA from the other domain. To verify the certificate signed by the other domain's CA, the principal obtains a certificate from his CA that certifies the public key of the other domain's CA.
Referring to FIG. 1 as an example, a principal Alice 1 in DOMAIN-A 10 wishes to authenticate or to communicate securely with a principal Bob 2 in DOMAIN-B 11. Bob 2 sends Alice 1 a certificate 20 certifying Bob's public key. Bob's certificate 20 is signed 21 by the DOMAIN-B CA. Alice 1 also obtains from Bob 2 or elsewhere (for example the DOMAIN-A CA), a certificate 25 for the DOMAIN-B CA signed 26 by the DOMAIN-A CA. This certificate contains the Domain-B CA's public key, and is signed by the Domain-A CA. Alice 1 can verify the DOMAIN-B CA's certificate 25, since Alice 1 knows the DOMAIN-A CA's public key. The verification process can include checking the CRL issued by the DOMAIN-A CA to determine that the certificate 25 certifying the DOMAIN B CA's public key has not been revoked. Once Alice 1 verifies DOMAIN-B CA's certificate 25, Alice 1 then “knows” the public key of the DOMAIN B CA. Alice 1 can verify Bob's certificate 20, by verifying that the certificate 20 was signed with the DOMAIN B CA's private key, and by checking the DOMAIN B CA's CRL to determine that Bob's certificate 20 has not been revoked.
Thus, as shown in the example of FIG. 1, the knowledge that Alice 1 has of her domain's CA's public key is used to verify certificates signed by other principals. In this example, Alice's domain's CA signed a certificate 25 containing the public key of another CA, which signed a certificate certifying Bob 2. This is a simple example of a certificate chain, in that Alice can authenticate or communicate with Bob 2 by verifying first the DOMAIN-B CA's certificate, and then the certificate 20 signed by the DOMAIN-B CA. A certificate chain can have any number of intermediary CA's. A certificate chain can be used for authentication or communication when the chain starts with a certificate including the public key of the desired communication or authentication partner, and ends with a certificate signed with a known public key.
Various types of security systems are known that use certificate chains. One such security system involves a hierarchy of CAs in which each principal is initially provided with the public key of a CA that is at the top of the hierarchy. Each CA below the top is verified by a certificate signed by the CA above it in the hierarchy, and so on. The principal trusts a certificate because it can follow the certificate signatures back to the top CA or other trusted root. Another system, referred to as a web of trust, doesn't use “official” CAs, and relies on principals to issue certificates for other principals. A principal who knows the public key of another principal, and trusts that other principal, can rely on a certificate signed by that principal to get the public key of a third principal. That third principal can sign a certificate with the public key of another principal, and so on. The principal verifies each certificate in the certificate chain from the person he wishes to communicate with to the person he trusts.
In the various systems, a first principal that wishes to verify a second principal's public key from a certificate chain verifies each certificate in the certificate chain from the principal to a trusted entity. This can be a time consuming process, since it can involve numerous public key cryptographic operations. In systems that use CRL's, this process is especially time consuming, because it requires obtaining the most recent CRL from each certificate-issuing entity. In some systems this overhead is incurred repeatedly as the same principal is repeatedly authenticated by the same principal, or by different principals within a subnetwork, or by principals within a domain, and so on, since each authenticating principal repeatedly verifies each certificate in the chain.
Referring to FIG. 2, which shows an example of a typical system of the prior art, a principal 40 has a chain of certificates 42 that can be used to verify the principal's 40 public key, and thereby enable authentication or secure communication with the principal 40. Each certificate in the chain of certificates 42 can be obtained from the same or different sources. To establish the identity of the principal 40 with other principals, in this example hosts 43A, 43B, 43C, generally 43, the principal 40 communicates the certificate chain 42 to each host 43. Each host 43 processes each certificate in the chain 42 to validate certificate format, lifetime, and other data 45. In addition, each host 43 accesses the Certificate Revocation List (“CRL”) 48 for each certificate in the chain. Also, each host 43 needs to maintain information 46 about principals that it trusts to have signed the last certificate in a chain (e.g. a list of CA's), referred to as trusted roots. The maintenance of a trusted root certificate list can be burdensome, because it requires that each, host be provided with the trusted root information in a secure manner.